Computer Science Notes: B-Tree Indexing & Mathematical Normalization

B-Tree Indexing Engine Architecture

Executing CREATE INDEX in SQL triggers the database engine to construct a sophisticated, self-balancing tree search data structure known as a B-Tree.

• Logarithmic Domination: A B-Tree maintains balanced depth across all leaf nodes, guaranteeing that search, insertion, and deletion operations evaluate to a definitive worst-case runtime complexity of O(log N).
• Disk I/O Minimization: B-Tree nodes are intentionally sized to align with underlying operating system memory pages (frequently 4KB), drastically curtailing the quantity of expensive physical disk reads required during complex queries.

Relational Algebra & Database Normalization

• First Normal Form (1NF): Requires that all column attributes maintain purely atomic values, strictly barring nested arrays or multi-value matrices.
• Second Normal Form (2NF): Mandates absolute elimination of partial dependencies, guaranteeing that non-key attributes depend entirely on the primary composite key.
• Third Normal Form (3NF): Demands the absolute severance of transitive dependencies, ensuring that non-key attributes never depend on other non-key attributes.

===================================================================================
                   RELATIONAL ALGEBRA / B-TREE COMPLEXITY
===================================================================================

  [ Flat CSV Search ]        ──> O(N) Worst-case linear disk scans
  [ B-Tree SQL Index ]       ──> O(log N) Self-balancing tree node lookups

===================================================================================